package main

import (
	"fmt"
	"local/algorithm/util"
)

/**
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
*/

/**
two pointer for size
时间复杂度O(n)
空间复杂度O(n)
双指针
*/
//*/
func lengthOfLongestSubstring(s string) int {
	maxSubStringLen := 0
	hm := make(map[byte]int)
	i, j := 0, 0

	for j = 0; j < len(s); j++ {
		if v, ok := hm[s[j]]; ok {
			if v >= i { //判断位置i之后是否出现重复字符，如果不是的话直接略过
				maxSubStringLen = util.Max(j-i, maxSubStringLen) //j-1-i+1 是位置i到j-1子串的长度
				i = v + 1                                        //hm中保存的是某字符的最后一次出现位置 pwwkew v处出现重复，调整序列开始位置从v+1开始
			}
		}

		hm[s[j]] = j //每次迭代后都要更新hm中的信息
	}

	return util.Max(maxSubStringLen, len(s)-i) //最后一次比较	(len(s)-1)-i+1
}

func main() {
	fmt.Println(lengthOfLongestSubstring("tmmzuxt"))
}

func maxLen(nums []int) int {
	maxLen := 0
	i, j := 0, 0
	m := make(map[int]int)

	for ; j < len(nums); j++ {
		curr := nums[j]
		if v, ok := m[curr]; ok && v >= i {
			maxLen = max(maxLen, j-1-i+1)
			i = v + 1
		}
		m[nums[j]] = j
	}

	return max(maxLen, len(nums)-1-i+1)
}
